Masala #0971
Sonlar o`qidagi girlyanda #2
Masalaning #1 va #2 versiyalari tubdan farq qiladi. Ularni alohida masalalar sifatida hisoblash to`g`riroqdir.
Yangi yilda arafasida, yangi yil ruhini bag`ishlovchi har xil bezak buyumlari mavjud. Asilbekka eng yoqgani - girlyandadir. Uni istalgan joyga ossa bo`ladi, devorga, mebelga, archaga... Asilbek esa girlyandani sonlar o`qiga osilganini ham ko`rgan!
Asilbek o`zining sevimli sonlar o`qining musbat tomoniga qarasa, u to`liq girlyanda bilan bezatilgan ekan. Bunda \(a\) va \(b(a \neq b)\) sonlar girlyanda bilan bog`langan, agarda \(a|b\) yoki \(b|a\) (bir sonni ikkinchisini qoldiqsiz bo`ladi) sharti qanoatlantirsa.
Payqash qiyin emaski, 1 sonidan girlyandalar orqali boshqa barcha sonlarga borish mumkin. Girlyanda orqali faqat katta songa o`tish mumkin bo`lsa, 1 sonidan \(A\) sonigacha eng ko`pi bilan nechta o`tish yordamida yetib olish mumkinligini oldin hisoblagan edik. Sizning endigi vazifangiz bunday o`tishlar sonini hisoblashdir.
Boshqa so`zlar bilan, 1 sonidan A sonigacha eng ko`p girlyandalar orqali o`tishning necha xil usuli mavjud?
Birinchi qatorda bitta butun son - \(T(1 \leq T \leq 2*10^5)\) testlar soni kiritiladi.
Keyingi \(T\) ta qatorning har birida bittadan butun son - \(A(2 \leq A \leq 10^7)\) soni kiritiladi.
Har bir test uchun yangi qatorda bitta butun son, masala javobini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 12 4 7 |
3 1 1 |
| 2 |
2 100 1 |
6 1 |
1-test:
12 ga yetib olish eng ko`pi bilan 3 ta girlyanda o`tishi orqali yetib borish mumkin. Bunday o`tishlar jami 3 xil.
1 -> 2 -> 4 -> 12
1 -> 2 -> 6 -> 12
1 -> 3 -> 6 -> 12
Telegram kanalimizga obuna bo'ling